<html lang="en-US">

<head>
    
<title>面试官：为什么 Go 的负载因子是 6.5？ - 花落雨忧</title>

<meta property="og:title" content="面试官：为什么 Go 的负载因子是 6.5？ - 花落雨忧">



    



    
    <meta property="description" content="大家好，我是煎鱼。
最近我有一个朋友，在网上看到一个有趣的段子，引发了我一些兴趣。
如下图：
听说是在最后的闲聊、吹水、聊人生、乱扯环节了，不是在技术环节了，所以大家也不用太在意什么技术评估法则（别杠）。
煎鱼作为一名技术号主，看到这里的 6.5，就想给大家挖一挖，这到底是何物，和大家一同学习和增长知识！
[&amp;hellip;] 实际上在 Go 语言中，就存在 6.5 这一概念，与 map 存在直接 &amp;hellip;">
    <meta property="og:description" content="大家好，我是煎鱼。
最近我有一个朋友，在网上看到一个有趣的段子，引发了我一些兴趣。
如下图：
听说是在最后的闲聊、吹水、聊人生、乱扯环节了，不是在技术环节了，所以大家也不用太在意什么技术评估法则（别杠）。
煎鱼作为一名技术号主，看到这里的 6.5，就想给大家挖一挖，这到底是何物，和大家一同学习和增长知识！
[&amp;hellip;] 实际上在 Go 语言中，就存在 6.5 这一概念，与 map 存在直接 &amp;hellip;">
    






<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="viewport" content="width=device-width,initial-scale=1">

<link rel="shortcut icon" href="https://www.lican.asia/logo/logo.png" type="image/x-icon" />



<link rel="stylesheet" href="/css/style.min.css" />

<link rel="stylesheet" href="/css/reset.min.css" />




<script src="https://www.lican.asia/js/highlight.min.js"></script>

<script>
hljs.configure({ ignoreUnescapedHTML: true })
hljs.highlightAll();
</script>


<script src="https://www.lican.asia/js/jquery.min.js"></script>




<link href="https://www.lican.asia/css/hugo-code.min.css" rel="stylesheet" />



    <style>
        .post-content img {
            max-width: 400px;
        }
    </style>
</head>

<body id="period" class="home blog">
    <a class="skip-content" href="#main">Press "Enter" to skip to content</a>
    <div id="overflow-container" class="overflow-container">
        <header class="site-header" id="site-header" role="banner">
    <div class="max-width">
        <div id="title-container" class="title-container">
            <div id="site-title" class="site-title"><a href="/">花落雨忧</a></div>
            <p class="tagline">思所及 力所行 方为真.</p>
        </div>
        
        <div id="menu-primary-container" class="menu-primary-container">
            <div class="icon-container">
            </div>
            <div id="menu-primary" class="menu-container menu-primary" role="navigation">
                <nav class="menu">
                    <ul id="menu-primary-items" class="menu-primary-items">
                        
                        
                        <li id="menu-item-0"
                            class="menu-item menu-item-type-custom menu-item-object-custom ">
                            <a href="/posts" aria-current="page" tabindex="0">首页</a></li>
                        
                        <li id="menu-item-1"
                            class="menu-item menu-item-type-custom menu-item-object-custom ">
                            <a href="/tech/" aria-current="page" tabindex="1">技术文档</a></li>
                        
                        <li id="menu-item-2"
                            class="menu-item menu-item-type-custom menu-item-object-custom ">
                            <a href="/article/" aria-current="page" tabindex="2">文章</a></li>
                        
                        <li id="menu-item-3"
                            class="menu-item menu-item-type-custom menu-item-object-custom ">
                            <a href="/project/" aria-current="page" tabindex="3">项目</a></li>
                        
                        <li id="menu-item-4"
                            class="menu-item menu-item-type-custom menu-item-object-custom ">
                            <a href="/about/" aria-current="page" tabindex="4">关于</a></li>
                        
                    </ul>
                </nav>
            </div>
        </div>
    </div>
</header>

        <div id="primary-container" class="primary-container">
            <div class="max-width">
                <section id="main" class="main" role="main">
                    <div id="loop-container" class="loop-container">
                        <div
                            class="post type-post status-publish format-standard hentry entry">
                            <article>
                                <div class="post-container">
                                    <div class="post-header">
                                        <h2 class="post-title">
                                            <a href="/posts/posts/go/map-65/">面试官：为什么 Go 的负载因子是 6.5？</a>
                                        </h2>
                                        
                                        <div class="post-byline">Published on
                                            <a class="date" href="javascript:;">2021/12/31</a>
                                            
                                            
                                            
                                            
                                            
                                        
                                    </div>
                                    <div class="post-content">
                                        <p>大家好，我是煎鱼。</p>
<p>最近我有一个朋友，在网上看到一个有趣的段子，引发了我一些兴趣。</p>
<p>如下图：</p>
<p><img src="https://files.mdnice.com/user/3610/e81547d8-8de7-4310-a62f-e59ce4c0def2.png" alt=""></p>
<p>听说是在最后的闲聊、吹水、聊人生、乱扯环节了，不是在技术环节了，所以大家也不用太在意什么技术评估法则（别杠）。</p>
<p>煎鱼作为一名技术号主，看到这里的 6.5，就想给大家挖一挖，这到底是何物，和大家一同学习和增长知识！</p>
<h2 id="65-是什么">6.5 是什么</h2>
<p>实际上在 Go 语言中，就存在 6.5 这一概念，与 map 存在直接关系，因此我们需要先了解 map 的基本数据结构，再介绍 6.5 的背景和由来。</p>
<p>开始学习 6.5 吧！</p>
<h3 id="了解-map-底层">了解 map 底层</h3>
<p>我以前在写《<a href="https://eddycjy.com/posts/go/map/2019-03-05-map-access/">深入理解 Go map：初始化和访问元素</a>》时有介绍过 map 的基础数据结构。</p>
<p>基本结构如下图：</p>
<p><img src="https://files.mdnice.com/user/3610/8679a84f-0d21-485d-b55f-dc9d70d5ddd1.png" alt="map 基本数据结构"></p>
<p>其中重要的一个基本单位是 hmap：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-golang" data-lang="golang"><span style="display:flex;"><span><span style="color:#66d9ef">type</span> <span style="color:#a6e22e">hmap</span> <span style="color:#66d9ef">struct</span> {
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">count</span>     <span style="color:#66d9ef">int</span>
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">flags</span>     <span style="color:#66d9ef">uint8</span>
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">B</span>         <span style="color:#66d9ef">uint8</span>
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">noverflow</span> <span style="color:#66d9ef">uint16</span>
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">hash0</span>     <span style="color:#66d9ef">uint32</span>
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">buckets</span>    <span style="color:#a6e22e">unsafe</span>.<span style="color:#a6e22e">Pointer</span>
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">oldbuckets</span> <span style="color:#a6e22e">unsafe</span>.<span style="color:#a6e22e">Pointer</span>
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">nevacuate</span>  <span style="color:#66d9ef">uintptr</span>
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">extra</span> <span style="color:#f92672">*</span><span style="color:#a6e22e">mapextra</span>
</span></span><span style="display:flex;"><span>}
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">type</span> <span style="color:#a6e22e">mapextra</span> <span style="color:#66d9ef">struct</span> {
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">overflow</span>    <span style="color:#f92672">*</span>[]<span style="color:#f92672">*</span><span style="color:#a6e22e">bmap</span>
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">oldoverflow</span> <span style="color:#f92672">*</span>[]<span style="color:#f92672">*</span><span style="color:#a6e22e">bmap</span>
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">nextOverflow</span> <span style="color:#f92672">*</span><span style="color:#a6e22e">bmap</span>
</span></span><span style="display:flex;"><span>}
</span></span></code></pre></div><ul>
<li>count：map 的大小，也就是 len() 的值，代指 map 中的键值对个数。</li>
<li>flags：状态标识，主要是 goroutine 写入和扩容机制的相关状态控制。并发读写的判断条件之一就是该值。</li>
<li>B：<strong>桶，最大可容纳的元素数量，值为 负载因子（默认 6.5） * 2 ^ B，是 2 的指数</strong>。</li>
<li>noverflow：溢出桶的数量。</li>
<li>hash0：哈希因子。</li>
<li>buckets：保存当前桶数据的指针地址（指向一段连续的内存地址，主要存储键值对数据）。</li>
<li>oldbuckets，保存旧桶的指针地址。</li>
<li>nevacuate：迁移进度。</li>
<li>extra：原有 buckets 满载后，会发生扩容动作，在 Go 的机制中使用了增量扩容，如下为细项：
<ul>
<li>overflow 为 hmap.buckets （当前）溢出桶的指针地址。</li>
<li>oldoverflow 为 hmap.oldbuckets （旧）溢出桶的指针地址。</li>
<li>nextOverflow 为空闲溢出桶的指针地址。</li>
</ul>
</li>
</ul>
<p>我们关注到 hmap 的 B 字段，其值就是 6.5，他就是我们在苦苦寻找的 6.5，但他又是什么呢？</p>
<h3 id="什么是负载因子">什么是负载因子</h3>
<p>B 值，这里就涉及到一个概念：<strong>负载因子（load factor），用于衡量当前哈希表中空间占用率的核心指标</strong>，也就是每个 bucket 桶存储的平均元素个数。</p>
<p>另外负载因子<strong>与扩容、迁移</strong>等重新散列（rehash）行为有直接关系：</p>
<ul>
<li>在程序运行时，会不断地进行插入、删除等，会导致 bucket 不均，内存利用率低，需要迁移。</li>
<li>在程序运行时，出现负载因子过大，需要做扩容，解决 bucket 过大的问题。</li>
</ul>
<p>负载因子是哈希表中的一个重要指标，在各种版本的哈希表实现中都有类似的东西，主要目的是<strong>为了平衡 buckets 的存储空间大小和查找元素时的性能高低</strong>。</p>
<p>在接触各种哈希表时都可以关注一下，做不同的对比，看看各家的考量。</p>
<h2 id="为什么是-65">为什么是 6.5</h2>
<p>了解是什么后，我们进一步深挖。</p>
<p>为什么 Go 语言中哈希表的负载因子是 6.5，为什么不是 8 ，也不是 1。这里面有可靠的数据支撑吗？</p>
<h3 id="测试报告">测试报告</h3>
<p>实际上这是 Go 官方的经过认真的测试得出的数字，一起来看看官方的这份测试报告。</p>
<p>报告中共包含 4 个关键指标，如下：</p>
<table>
<thead>
<tr>
<th>loadFactor</th>
<th>%overflow</th>
<th>bytes/entry</th>
<th>hitprobe</th>
<th>missprobe</th>
</tr>
</thead>
<tbody>
<tr>
<td>4.00</td>
<td>2.13</td>
<td>20.77</td>
<td>3.00</td>
<td>4.00</td>
</tr>
<tr>
<td>4.50</td>
<td>4.05</td>
<td>17.30</td>
<td>3.25</td>
<td>4.50</td>
</tr>
<tr>
<td>5.00</td>
<td>6.85</td>
<td>14.77</td>
<td>3.50</td>
<td>5.00</td>
</tr>
<tr>
<td>5.50</td>
<td>10.55</td>
<td>12.94</td>
<td>3.75</td>
<td>5.50</td>
</tr>
<tr>
<td>6.00</td>
<td>15.27</td>
<td>11.67</td>
<td>4.00</td>
<td>6.00</td>
</tr>
<tr>
<td>6.50</td>
<td>20.90</td>
<td>10.79</td>
<td>4.25</td>
<td>6.50</td>
</tr>
<tr>
<td>7.00</td>
<td>27.14</td>
<td>10.15</td>
<td>4.50</td>
<td>7.00</td>
</tr>
<tr>
<td>7.50</td>
<td>34.03</td>
<td>9.73</td>
<td>4.75</td>
<td>7.50</td>
</tr>
<tr>
<td>8.00</td>
<td>41.10</td>
<td>9.40</td>
<td>5.00</td>
<td>8.00</td>
</tr>
</tbody>
</table>
<ul>
<li>loadFactor：负载因子，也有叫装载因子。</li>
<li>%overflow：溢出率，有溢出 bukcet 的百分比。</li>
<li>bytes/entry：每对 key/elem 的开销字节数.</li>
<li>hitprobe：查找一个存在的 key 时，要查找的平均个数。</li>
<li>missprobe：查找一个不存在的 key 时，要查找的平均个数。</li>
</ul>
<h3 id="选择数值">选择数值</h3>
<p>结合测试报告一看，好家伙，不测不知道，一测吓一跳，有依据了。</p>
<p>Go 官方发现：<strong>负载因子太大了，会有很多溢出的桶。太小了，就会浪费很多空间</strong>（too large and we have lots of overflow buckets, too small and we waste a lot of space）。</p>
<p><img src="https://files.mdnice.com/user/3610/93b87f8d-a0ad-4503-b4f9-e3cf040468df.png" alt="来自 Go 官方源码说明"></p>
<p>根据这份测试结果和讨论，Go 官方把 Go 中的 map 的负载因子硬编码为 6.5，这就是 6.5 的选择缘由。</p>
<p>这意味着在 Go 语言中，<strong>当 B（bucket）平均每个存储的元素大于或等于 6.5 时，就会触发扩容行为</strong>，这是作为我们用户对这个数值最近的接触。</p>
<h2 id="总结">总结</h2>
<p>在今天这篇文章中，我们先快速了解了 Go 语言中 map 的基本数据结构和设计，这和我们要解释的问题紧密相关。</p>
<p>紧接着针对开头所提出的 6.5，进行了介绍和说明，这其实是 map 中的负载因子。其数值的确定来源于 Go 官方的测试。</p>
<p>为什么是 6.5，你懂了吗？</p>
<h2 id="参考">参考</h2>
<ul>
<li><a href="https://golang.org/src/runtime/map.go">src/runtime/map.go</a></li>
<li><a href="https://juejin.cn/post/6954707500151078919">深度解析golang map</a></li>
<li><a href="https://zhuanlan.zhihu.com/p/366472077">golang中map底层B值的计算逻辑</a></li>
</ul>


                                        
                                        
                                        
                                        <div class="rp4wp-related-posts">
                                            <h3>相关文章</h3>
                                            <ul>
                                                
                                                <li>
                                                    <div class="rp4wp-related-post-content">
                                                        <a
                                                            href="https://www.lican.asia/posts/posts/go/map-reset/">Go map 如何缩容？</a>
                                                    </div>
                                                </li>
                                                
                                                <li>
                                                    <div class="rp4wp-related-post-content">
                                                        <a
                                                            href="https://www.lican.asia/posts/posts/go/sync-map/">Go 并发读写 sync.map 的强大之处</a>
                                                    </div>
                                                </li>
                                                
                                                <li>
                                                    <div class="rp4wp-related-post-content">
                                                        <a
                                                            href="https://www.lican.asia/posts/posts/go/map-slice-concurrency/">为什么 Go map 和 slice 是非线程安全的？</a>
                                                    </div>
                                                </li>
                                                
                                                <li>
                                                    <div class="rp4wp-related-post-content">
                                                        <a
                                                            href="https://www.lican.asia/posts/posts/go/gmp-why-p/">经典面试题：你觉得 Go 在什么时候会抢占 P？</a>
                                                    </div>
                                                </li>
                                                
                                                <li>
                                                    <div class="rp4wp-related-post-content">
                                                        <a
                                                            href="https://www.lican.asia/posts/posts/go/goroutine-leak/">跟面试官聊 Goroutine 泄露的 6 种方法，真刺激！</a>
                                                    </div>
                                                </li>
                                                
                                            </ul>
                                        </div>
                                        
                                        
                                    </div>

                                    
                                    
                                    

                                    
                                    <div class="post-meta">
                                        
                                        
                                        <div class="post-tags">
                                            <ul>
                                            
                                            <li>
                                                <a href="/tags/go" title="View all posts tagged match">go</a>
                                            </li>
                                            
                                            <li>
                                                <a href="/tags/%e9%9d%a2%e8%af%95%e9%a2%98" title="View all posts tagged match">面试题</a>
                                            </li>
                                            
                                            </ul>
                                        </div>
                                        
                                        
                                        <nav class="further-reading">
                                            
                                            <div class="previous">
                                                <span>&lt;&lt; Prev</span>
                                                <a href="https://www.lican.asia/posts/posts/go/slice-discuss/"
                                                    rel="prev">Go 切片这道题，吵了一个下午！</a> </div>
                                            
                                            
                                            <div class="next">
                                                <span>Next >></span>
                                                <a href="https://www.lican.asia/posts/posts/go/map-reset/">Go map 如何缩容？</a> 
                                            </div>
                                            
                                        </nav>
                                    </div>
                                    
                                    

                                    
                                    
                                    

                                </div>
                            </article>
                        </div>
                    </div>
                </section>
                <aside class="sidebar sidebar-primary" id="sidebar-primary" role="complementary">
    <h1 class="screen-reader-text">Sidebar</h1>
    

    
    
    <section id="text-2" class="widget widget_text">
        <div class="textwidget">
            
            <div id="profile">
                <div id="profile_picture"><img src="https://www.lican.asia/logo/logo.png"></div>
                <div id="profile_intro">
                    <p><span class="name">Lican</span></p>
                    <p class="intro">全栈开发者，爱好造轮子。</p>
                </div>
            </div>
            
            <p>
                <script type="text/javascript">
                    (function ($) {
                        $(document).ready(function () {
                            var menuPrimaryContainer = $('#menu-primary-container');
                            var profile = $('#text-2');
                            $('#toggle-navigation').click(function () {
                                if (menuPrimaryContainer.hasClass('open')) {
                                    profile.removeClass('open');
                                } else {
                                    profile.addClass('open');
                                }
                            });
                        });
                    })(jQuery);
                </script>
            </p>
        </div>
    </section>
    
    
    
    
    
    <section id="text-5" class="widget widget_text">
        <h2 class="widget-title">开源项目</h2>
        <div class="textwidget">
            <div id="projects" style="line-height: 22px;">
                
                <a href="https://github.com/idoubi/gonews"
                    target="_blank">gonews</a>: &nbsp;Daily news for golang<br>
                
                <a href="https://github.com/idoubi/sql2struct"
                    target="_blank">sql2struct</a>: &nbsp;Generate go struct according to SQL<br>
                
                <a href="https://github.com/idoubi/goz"
                    target="_blank">goz</a>: &nbsp;Request library used in golang<br>
                
        </div>
    </section>
    
    

    
    
    
    
    <section id="qrcode" class="widget widget_media_image">
        <h2 class="widget-title">微信公众号</h2>
        <img width="258" height="258"
            src="https://www.lican.asia/wechat/lican.png"
            class="image wp-image-5514  attachment-full size-full" alt=""
            style="max-width: 100%; height: auto;"
            sizes="(max-width: 258px) 100vw, 258px">
    </section>
    
    

    
    
    

    
    
    

    
    
    
    
</aside>
            </div>
        </div>

        <footer id="site-footer" class="site-footer" role="contentinfo">
    <div class="max-width">
    </div>
    <div class="footer">
        <div id="footercontent">
            © lican.asia All rights reserved<br/>
            Built with Hugo Theme <a href="https://github.com/idoubi/hugo-theme-period" target="_blank">Period</a>
        </div>
    </div>
</footer>

<script>
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?e8351b6d4626d5881d439ea1f6184baa";
      var s = document.getElementsByTagName("script")[0]; 
      s.parentNode.insertBefore(hm, s);
    })();
</script>
    
    
    </div>
    
</body>

</html>